package com.demo.datastructure.string;

/**
 * @Author： ljr
 * @Description： bm算法的实现 (书读百遍, 其义自现)
 * @Date： 2022/7/22 11:24 AM
 */
public class BmString {

    private static final int SIZE = 256; // 全局变量或成员变量
    private void generateBC(char[] b, int m, int[] bc) {
        for (int i = 0; i < SIZE; ++i) {
            bc[i] = -1; // 初始化bc
        }

        for (int i = 0; i < m; ++i) {
            int ascii = (int)b[i]; // 计算b[i]的ASCII值
            bc[ascii] = i;
        }
    }


    public int bm(char[] a, int n, char[] b, int m){
        int[] bc = new int[SIZE];
        generateBC(b, m, bc);
        int[] suffix = new int[m];
        boolean[] prefix = new boolean[m];
        generateGS(b, m, suffix, prefix);
        int i = 0;
        while(i <= n - m){
            int j;
            for (j = m-1; j > -1; --j) {
                if(b[j] != a[i + j]){
                    break;
                }
            }

            if(j < 0){
                return i;
            }
            int x = j - bc[(int)a[i+j]];

            int y = 0;
            if(j < m -1){
                y = moveByGs(j, m, suffix, prefix);
            }
            i = i + Math.max(x, y);
        }
        return -1;
    }

    private int moveByGs(int j, int m, int[] suffix, boolean[] prefix) {
        int k = m - 1 - j;
        if(suffix[k] > -1) return j - suffix[k] + 1;
        for(int r = j + 2; r <= m -1; ++ r){
            if(prefix[m - r] == true){
                return r;
            }
        }

        return m;
    }


    // b表示模式串，m表示长度，suffix，prefix数组事先申请好了
    private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
        for (int i = 0; i < m; ++i) { // 初始化
            suffix[i] = -1;
            prefix[i] = false;
        }

        for (int i = 0; i < m - 1; ++i) { // b[0, i]
            int j = i;
            int k = 0; // 公共后缀子串长度
            while (j >= 0 && b[j] == b[m-1-k]) { // 与b[0, m-1]求公共后缀子串
                --j;
                ++k;
                suffix[k] = j+1; //j+1表示公共后缀子串在b[0, i]中的起始下标
            }
            if (j == -1) prefix[k] = true; //如果公共后缀子串也是模式串的前缀子串
        }
    }


    public static void main(String[] args) {
        char[] b = new char[]{'c', 'a', 'b', 'c', 'a', 'b'};
        int[] suffix = new int[b.length];
        boolean[] prefix = new boolean[b.length];
        BmString bmString = new BmString();
        bmString.generateGS(b, b.length, suffix, prefix);


    }
}
